package 剑指offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-11-24 10:53
 * 搜索和回溯
 */
public class day14_12_13 {

    /**===========================================================================================================================
     * 剑指 Offer 12. 矩阵中的路径
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     * 回溯：
     * 路径：已经选择过的网格中的节点
     * 选择列表：相邻单元格中没有被选择过的
     * 终止条件：word到最后一个，全部匹配成功
     * */
    //对board[i][j]位置，word中的index是否可以匹配
    boolean backtrack12(char[][] board,String word,int index,int i,int j){
        //base case
        if (i>=board.length||i<0||j>=board[0].length||j<0) return false;
        if (board[i][j]!=word.charAt(index)) return false;
        if (index==word.length()-1) return true;
        //做出选择：将board[i][j]位置置为#，表示已经访问过了
        board[i][j]='#';
        //遍历选择列表,上下左右
        boolean res=backtrack12(board,word,index+1,i-1,j)||backtrack12(board,word,index+1,i+1,j)||
                backtrack12(board,word,index+1,i,j-1)||backtrack12(board,word,index+1,i,j+1);
        //撤销选择
        board[i][j]=word.charAt(index);
        return res;
    }

    public boolean exist(char[][] board, String word) {
        //对每个元素作为开始进行回溯
        int m=board.length,n=board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtrack12(board,word,0,i,j)) return true;
            }
        }
        return false;
    }


    /**===========================================================================================================================
     * 剑指 Offer 13. 机器人的运动范围
     * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
     * 也不能进入行坐标和列坐标的数位之和大于k的格子。请问该机器人能够到达多少个格子？
     *
     * 回溯：
     * 路径：已经到达过的格子
     * 选择列表：相邻单元格中没有被选择过的且满足条件的
     * 终止条件：遍历完全部单元格
     * */
    List<String> res13=new ArrayList<>();
    void backtrack13(int m,int n,int k,int i,int j){
        //base case
        if (i<0||i>=m||j<0||j>=n) return;
        String key=i+","+j;
        if (getSumOfIndex(i)+getSumOfIndex(j)>k||res13.contains(key)) return;
        //做出选择
        res13.add(key);
        //上下左右
        backtrack13(m,n,k,i-1,j);
        backtrack13(m,n,k,i+1,j);
        backtrack13(m,n,k,i,j-1);
        backtrack13(m,n,k,i,j+1);
        //res13.remove(key);
    }
    int getSumOfIndex(int n){
        int res=0;
        while (n!=0){
            res+=n%10;
            n=n/10;
        }
        return res;
    }
    public int movingCount1(int m, int n, int k) {
        backtrack13(m,n,k,0,0);
        return res13.size();
    }

    //DFS深度优先
    int m,n,k;
    boolean[][] visited;
    int dfs(int i,int j){
        if (i>=m||j>=n||k<getSumOfIndex(i)+getSumOfIndex(j)||visited[i][j])return 0;
        visited[i][j]=true;
        return 1+dfs(i+1,j)+dfs(i,j+1);
    }
    public int movingCount(int m, int n, int k) {
        if (k==0) return 1;
        this.m=m;this.n=n;this.k=k;
        this.visited=new boolean[m][n];
        return dfs(0,0);
    }
}
